package com.atguigu.prim;

import java.util.Arrays;

public class PrimDemo {
    public static void main(String[] args) {
        char[] vertexs=new char[]{'A','B','C','D','E','F','G'};
        int[][] weights=new int[][]{
                {10000,5,7,10000,10000,10000,2},
                {5,10000,10000,9,10000,10000,3},
                {7,10000,10000,10000,8,10000,10000},
                {10000,9,10000,10000,10000,4,10000},
                {10000,10000,8,10000,10000,5,4},
                {10000,10000,10000,4,5,10000,6},
                {2,3,10000,10000,4,6,10000}
        };
        MyGraph graph = new MyGraph(vertexs.length);

        MinTree minTree = new MinTree();
        minTree.create(graph,vertexs,weights);

        graph.print();

        minTree.prim(graph,0);

    }
}

class MinTree{
    public void create(MyGraph graph, char[] vertexs,int[][] weights){
        System.arraycopy(vertexs, 0, graph.vertexs, 0, vertexs.length);

        for(int i=0;i<vertexs.length;i++){
            System.arraycopy(weights[i], 0, graph.weights[i], 0, vertexs.length);
        }
    }

    public void prim(MyGraph graph,int startVisit){
        int[] visited=new int[graph.vertexSize];
        visited[startVisit]=1;

        int minWeight=10000;
        int h1=-1;
        int h2=-1;
        for(int vertexIndex=0;vertexIndex<visited.length;vertexIndex++){
            if(vertexIndex==startVisit){
                continue;
            }
            for (int i = 0; i < graph.weights.length; i++) {
                if(visited[i]==0){
                    continue;
                }
                for(int j=0;j< graph.weights[i].length;j++){
                    if(visited[j]==0&&graph.weights[i][j]<minWeight){
                        minWeight=graph.weights[i][j];
                        h1=i;
                        h2=j;
                    }
                }
            }
            System.out.printf("链接%c与%c, 权值=%d\n",graph.vertexs[h1],graph.vertexs[h2],minWeight);
            visited[h2]=1;
            minWeight=10000;
            h1=-1;
            h2=-1;

        }

    }

}

class MyGraph{
    int vertexSize;
    char[] vertexs;
    int[][] weights;

    public MyGraph(int vertexSize) {
        this.vertexSize = vertexSize;
        vertexs=new char[vertexSize];
        weights=new int[vertexSize][vertexSize];
    }

    public void print(){
        for (int[] weight : weights) {
            System.out.println(Arrays.toString(weight));
        }
    }
}
